const int N = 1e5 + 10;
const int M = 1010;
int id[N],L[M],R[M],len;//L为块i的左边界，R为块i的右边界，be表示第某个点所在的块
                        //id 表示块的编号, len=sqrt(n),sqrt的时候时间复杂度最优
long long a[50005], b[50005], s[50005];
// a 数组表示数据数组, b 数组记录每个块的整体赋值情况, 类似于 lazy_tag, 
// s表示块内元素总和
void cg(int k)
{ 
    for(int i = L[k]; i <= R[k]; i++)
    {
        s[k] += a[i];
    }
}
void add(int l, int r, long long x) 
{  
    // 区间加法
    int sid = id[l], eid = id[r];
    if (sid == eid) 
    {  // 在一个块中
        for (int i = l; i <= r; i++) 
        {
            a[i] += x;
            s[sid] += x;
        }
        return;
    }
    for(int i = l; i <= R[id[l]]; i++) //除去完整块，遍历左块
    {
        a[i] += x;
        s[sid] += x;
    }
    for(int i = id[l] + 1; i <= id[r] - 1; i++)//遍历每一个完整块
    {
        b[i] += x;
        s[i] += len * x;  // 更新区间和数组(完整的块)
    }
    for(int i = L[id[r]]; i <= r; i++) //除去完整块，遍历右块
    {
        a[i] += x;
        s[eid] += x;
    }
    // 以上两行不完整的块直接简单求和
}
long long query(int l, int r, long long p) 
{  
    // 区间查询
    int sid = id[l], eid = id[r];
    long long ans = 0;
    if (sid == eid) 
    {   // 在一个块里直接暴力求和
        for (int i = l; i <= r; i++) 
        {
            ans = (ans + a[i] + b[sid]) % p;
        }
        return ans;
    }
    for(int i = l; i <= R[id[l]]; i++) //除去完整块，遍历左块
    {
        ans = (ans + a[i] + b[sid]) % p;
    }
    for(int i = id[l] + 1; i <= id[r] - 1; i++)//遍历每一个完整块
    {
        ans = (ans + s[i]) % p;
    }
    for(int i = L[id[r]]; i <= r; i++) //除去完整块，遍历右块
    {
        ans = (ans + a[i] + b[eid]) % p;
    }
    // 和上面的区间修改是一个道理
    return ans;
}
int main() 
{
    int n;
    cin >> n;
    len = sqrt(n);  // 均值不等式可知复杂度最优为根号n
    int ct = (n + len - 1) / len;//块的数量
    for (int i = 1; i <= n; i++) 
    {  
        cin >> a[i];
    }
    for(int i = 1; i <= ct; i++)
    {
        L[i] = (i - 1) * len + 1;//L为块i的左边界，R为块i的右边界
        R[i] = min(n, i * len);
        for(int j = L[i]; j <= R[i]; j++)
        {
            id[j] = i;//id表示第某个点所在的块
        }
        cg(i);//初始化每个块
    }
    for (int i = 1; i <= n; i++) 
    {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (op == 0)
            add(l, r, c);
        else
            cout << query(l, r, c + 1) << endl;
    }
    return 0;
}